---
title: "L2-029 特立独行的幸福"
created: 2025-11-28
tags:
  - 算法
---

# L2-029 特立独行的幸福

## 题目 [L2-029 特立独行的幸福](https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7?page=1&problemSetProblemId=1111914599412858886)

![[image-44e5405e.png]]

## 思路分析

![[image-36329077.png]]

- 每个数字 `i` 进行 DFS 路径模拟，记录所有中间值。
- 如果最后成功到达 1，说明是幸福数。
- 如果其他幸福数出现在路径中，则这些中间值是依附于 `i` 的。
- 不依附于他人的幸福数就是特立独行的幸福数，输出其独立性。

## 代码实现

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
using ull = unsigned long long;
using PII = pair<int ,int>;
using Pll = pair<ll,ll>;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

unordered_map<int,bool> isHappy;
unordered_map<int,bool> notIndependent;
unordered_map<int,int> indepCount;

bool isPrime(int n){
	if(n<=1)	return false;
	for(int i=2;i<=n/i;i++){
		if(n%i==0)	return false;
	}
	return true;
}

int nextNum(int n){
	int sum=0;
	while(n){
		sum+=(n%10)*(n%10);
		n/=10;
	}
	return sum;
}

bool dfs(int cur,unordered_set<int>& path,vector<int>& route){
	if(cur==1)	return true;
	if(path.count(cur))	return false;
	path.insert(cur);
	route.push_back(cur);

	int nxt=nextNum(cur);
	bool result=dfs(nxt,path,route);
	return result;
}

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int l,r;cin>>l>>r;
	vector<int> happyNums;
	for(int i=l;i<=r;i++){
		unordered_set<int> visited; // 判断是否死循环
		vector<int> route; // 记录路径（得到依赖于当前数的幸福数个数）
		bool happy = dfs(i,visited,route);

		if(happy){
			isHappy[i]=true;
			for(int j:route){
				if(j!=i){
					notIndependent[j]=true; //除第一个外 其他都不独立
				}
				indepCount[i]++;
			}
			happyNums.push_back(i);
		}
	}

	bool found=false;
	sort(happyNums.begin(),happyNums.end());
	for(int n:happyNums){
		if(!notIndependent[n]){
			int score = indepCount[n];
			if(isPrime(n))	score*=2;
			cout<<n<<" "<<score<<endl;
			found=true;
		}
	}

	if(!found)	cout<<"SAD"<<endl;

	return 0;
}
```

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

using ll = long long;

using ull = unsigned long long;

using PII = pair<int,int>;

using Pll = pair<ll,ll>;

int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

const int inf = 0x3f3f3f3f;

unordered_map<int,bool> isNotdependent;

unordered_map<int,int> dependentCnt;

bool is_prime(int n){

	if(n<2)	return false;

	for(int i=2;i<=n/i;i++){

		if(n%i==0){

			return false;

		}

	}

	return true;

}

int nextNum(int i){

	ll sum=0;

	while(i){

		int cur=i%10;

		sum+=cur*cur;

		i/=10;

	}

	return sum;

}

bool dfs(int cur,unordered_set<int>& visited,vector<int>& route){

	if(cur==1)	return true;

	if(visited.find(cur)!=visited.end())	return false;

	visited.insert(cur);

	route.push_back(cur);

	int nxt=nextNum(cur);

	return dfs(nxt,visited,route);

}

int main(){

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	int l,r;cin>>l>>r;

	vector<int> happyNums;

	for(int i=l;i<=r;i++){

		unordered_set<int> visited;

		vector<int> route;

		bool happy=dfs(i,visited,route);

		if(happy){

			for(auto j:route){

				if(j!=i){

					isNotdependent[j]=true;

				}

				dependentCnt[i]++;

			}

			happyNums.push_back(i);

		}

	}

	bool found=false;

	sort(happyNums.begin(),happyNums.end());

	for(int n:happyNums){

		if(!isNotdependent[n]){

			int score=dependentCnt[n];

			if(is_prime(n))

				score*=2;

			cout<<n<<" "<<score<<endl;

			found=true;

		}

	}

	if(!found)	cout<<"SAD"<<endl;

	return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[L2-028 秀恩爱分得快|L2-028 秀恩爱分得快]] 🏠 [[00-天梯赛]] ➡️ [[L2-030 冰岛人|L2-030 冰岛人]]